package _1_leetcode_1_20._19删除链表的倒数第N节点;

import java.util.Stack;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 *
 * @描述
 * @参数
 * @返回值
 * @创建人 mazexal
 * @创建时间 2021/1/8
 */
public class Solution {


    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2));
        ListNode tmp = removeNthFromEnd(head, 2);
        System.out.println(tmp);
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;
        ListNode tmp = virtualHead;
        Stack<ListNode> stack = new Stack();
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            ListNode prev = stack.pop();
            prev.next = prev.next.next;
        } else {
            return null;
        }
        return virtualHead.next;
    }
}
